0% completed
Problem Statement
Given an array of positive integers height, where height[i] represents the height of the bar in the elevation map and each bar has width 1, return how much water it can trap after raining.
Examples
Example 1:
- Input: height =
[4, 0, 3, 0, 2]
- Expected Output:
5 - Justification: The first and third bars form a container that traps 3 units of water. The third and fifth bars trap an additional 2 units. Therefore, the total trapped water is 5 units.
Example 2:
- Input: height =
[1, 2, 1, 2, 1]
- Expected Output:
1 - Justification: Water is only trapped between the second and fourth bars, holding 1 unit of water.
Example 3:
- Input: height =
[3, 1, 2, 4, 0, 1, 3]
- Expected Output:
8 - Justification: The first, and fourth bars trap 3 units of water. The fourth, and seventh bars trap an additional 5 units. The total is 8 units of trapped water.
Constraints:
- n == height.length
- 1 <= n <= 2 * 104
- 0 <= height[i] <= 105
Solution
To solve this problem, we'll employ a two-pointer technique, which is efficient for this kind of linear space problem. This approach works by iterating over the elevation map from both ends towards the center, calculating the potential water trap at each step. We believe this method is effective because it allows us to compute the maximum water trapped by considering the minimum height between two points at a time, which is the limiting factor for water trapping. This way, we can efficiently calculate the trapped water without needing to consider all possible containers formed between bars, significantly reducing the computational complexity.
The essence of our approach is to keep track of the left and right maximum heights as we move the pointers towards the center. By comparing these heights, we can determine the amount of water that can be trapped at each step based on the difference between the current height and the minimum of the two maximum heights. This strategy ensures that we only need to pass through the elevation map once, making it a highly efficient solution.
Step-by-Step Algorithm
-
Initialize Pointers and Variables:
- Set two pointers,
leftandright, to point at the start and end of the array, respectively. - Initialize two variables,
leftMaxandrightMax, to0. These will keep track of the maximum height encountered so far from the left and right sides. - Initialize a variable
waterTrappedto0. This will accumulate the total amount of water trapped.
- Set two pointers,
-
Iterate Over the Array:
- While the
leftpointer is less than therightpointer, do the following:- Compare the height at the
leftpointer with the height at therightpointer. - If the height at
leftis less than the height atright:- Update
leftMaxto the maximum ofleftMaxand the height at the currentleftposition. - Calculate the water trapped at the current
leftposition as the difference betweenleftMaxand the height atleft, and add it towaterTrapped. If the difference is negative, add0instead. - Increment the
leftpointer to move it towards the center.
- Update
- Else (if the height at
rightis less than or equal to the height atleft):- Update
rightMaxto the maximum ofrightMaxand the height at the currentrightposition. - Calculate the water trapped at the current
rightposition as the difference betweenrightMaxand the height atright, and add it towaterTrapped. If the difference is negative, add0instead. - Decrement the
rightpointer to move it towards the center.
- Update
- Compare the height at the
- While the
-
Return the Total Water Trapped:
- After the loop terminates (when
leftmeetsright), return thewaterTrappedvariable as the total amount of water trapped.
- After the loop terminates (when
Algorithm Walkthrough
Let's consider the input: height = [3, 1, 2, 4, 0, 1, 3].
-
Initialization:
left = 0,right = 6,leftMax = 0,rightMax = 0,waterTrapped = 0
-
First Iteration:
left = 0,right = 6,height[left] = 3,height[right] = 3- Since
height[left]is not less thanheight[right], we look to updaterightMaxand calculate water forright. rightMaxis updated to3.- No water is trapped because
rightMaxequalsheight[right]. - Decrement
right. waterTrapped = 0.
-
Second Iteration:
left = 0,right = 5,height[left] = 3,height[right] = 1height[left]is greater thanheight[right], so we updaterightMaxif needed and calculate water forright.rightMaxremains3.- Water trapped at
right = 5is3 - 1 = 2. - Decrement
right. waterTrapped = 2.
-
Third Iteration:
left = 0,right = 4,height[left] = 3,height[right] = 0rightMaxremains3.- Water trapped at
right = 4is3 - 0 = 3. - Decrement
right. waterTrapped = 5.
-
Fourth Iteration:
left = 0,right = 3,height[left] = 3,height[right] = 4leftMaxremains3.- No water is trapped because
leftMaxequalsheight[left]. - Increment
left. waterTrapped = 5.
-
Fifth Iteration:
left = 1,right = 3,height[left] = 1,height[right] = 4leftMaxremains3.- Water trapped at
left = 1is3 - 1 = 2. - Increment
left. waterTrapped = 7.
-
Sixth Iteration:
left = 2,right = 3,height[left] = 2,height[right] = 4leftMaxremains3.- Water trapped at
left = 2is3 - 2 = 1. - Increment
left. waterTrapped = 8.
-
Seventh Iteration:
- The loop terminates because
leftis no longer less thanright.
- The loop terminates because
-
Conclusion:
- The total
waterTrappedis8.
- The total
Code
Complexity Analysis
Time Complexity
The time complexity of the algorithm is
Space Complexity
The space complexity of the algorithm is
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Code
Complexity Analysis
Time Complexity
Space Complexity